/**

 * ...

 * @author Thot

 */



function BSPTree(){}


BSPTree.frame					= 0;
BSPTree.X_AXIS					= "x_axis";
BSPTree.Y_AXIS					= "y_axis";


BSPTree.prototype.n 			= 0;		// tree depth
BSPTree.prototype.parentNode 	= null;
BSPTree.prototype.front 		= null;
BSPTree.prototype.back 			= null;
BSPTree.prototype.children		= new Array();
BSPTree.prototype.axis			= BSPTree.X_AXIS;


BSPTree.prototype.depthLimit	= 10;
BSPTree.prototype.childrenLimit	= 50;
BSPTree.prototype.isLeaf		= true;
BSPTree.prototype.width			= 0;
BSPTree.prototype.x				= 0;
BSPTree.prototype.y				= 0;
BSPTree.prototype.height		= 0;
BSPTree.prototype.limit			= 0;
BSPTree.prototype.axisP1		= "";
BSPTree.prototype.axisP2		= "";



BSPTree.prototype.addChild 	= function( p_child )
{
	
	var i = 0;
	var l_max = 0;
	
	
	if( this.isLeaf )
	{
		this.children.push( p_child );
	}
	else
	{
		this.addElement( p_child, this.limit, this.axisP1, this.axisP2);
	}
	
	
	if( this.children.length > this.childrenLimit && this.n < this.depthLimit )
	{
		
		this.createBackAndFront();
		
		l_max = this.children.length;
		
		for( i = 0; i < l_max; i++ )
		{
			this.addElement( this.children[i], this.limit, this.axisP1, this.axisP2);
		}
		
		this.children = new Array();
		
	}
	
	
};


BSPTree.prototype.addElement = function( p_child, p_limit, p_p1, p_p2 )
{
	if( ( p_child[p_p1] ) < p_limit )
	{
		if( ( p_child[p_p1] + p_child[p_p2] ) >= p_limit )
		{
			this.front.addChild( p_child );
		}
		
		this.back.addChild( p_child );
	}
	else
	{
		this.front.addChild( p_child );
	}
};


BSPTree.prototype.removeChild = function( p_child )
{
	var l_index = this.children.indexOf( p_child );
	
	if( this.isLeaf || l_index != -1 )
	{
		if( l_index != -1 )
		{
			this.children.splice( l_index , 1 );
		}
	}
	else
	{
		this.front.removeChild( p_child );
		this.back.removeChild( p_child );
	}
};


BSPTree.prototype.createBackAndFront = function()
{
	
	
	this.back 	= new BSPTree();
	this.front 	= new BSPTree();
	
	
	if( this.axis == BSPTree.X_AXIS )
	{
		
		
		this.back.init( 	this.x, 
							this.y, 
							this.width * 0.5, 	
							this.height,
							this.n + 1, 
							BSPTree.Y_AXIS, 
							this,
							this.depthLimit,
							this.childrenLimit );
		
		this.front.init( 	this.x + ( this.width * 0.5 ),
							this.y, 
							this.width * 0.5, 	
							this.height, 
							this.n + 1, 
							BSPTree.Y_AXIS, 
							this,
							this.depthLimit,
							this.childrenLimit );
	}
	else
	{
		
		
		this.back.init( 	this.x, 
							this.y, 
							this.width, 	
							this.height * 0.5, 
							this.n + 1, 
							BSPTree.X_AXIS, 
							this,
							this.depthLimit,
							this.childrenLimit );
		
		
		this.front.init( 	this.x, 
							this.y + ( this.height * 0.5 ),
							this.width,	
							this.height * 0.5, 
							this.n + 1, 
							BSPTree.X_AXIS, 
							this,
							this.depthLimit,
							this.childrenLimit );
	}

	this.isLeaf = false;

};


BSPTree.prototype.init 	= function( p_x, p_y, p_width, p_height, p_n, p_axis, p_parentNode, p_nLimit, p_cLimit )
{
	
	this.x 			= p_x;
	this.y 			= p_y;
	this.width 		= p_width;
	this.height 	= p_height;
	this.axis 		= p_axis;
	this.parentNode = p_parentNode;
	this.n 			= p_n;
	this.children 	= new Array();
	this.isLeaf 	= true;
	this.limit 		= ( this.axis == BSPTree.X_AXIS ) ? this.x + ( this.width * 0.5 ) : this.y + ( this.height * 0.5 );
	this.axisP1 	= ( this.axis == BSPTree.X_AXIS ) ? "x" : "y";
	this.axisP2 	= ( this.axis == BSPTree.X_AXIS ) ? "width" : "height";
	this.childrenLimit  = p_cLimit;
	this.depthLimit 	= p_nLimit;

};


// traversal methods



BSPTree.prototype.getVisibleChildrenIn = function ( p_x, p_y, p_width, p_height )
{
	var children = this.getVisibleChildrenRecursive( p_x, p_y, p_width, p_height );
	return this.filter( children, p_x, p_y, p_width, p_height );
}

BSPTree.prototype.getVisibleChildrenIterative 	= function( p_x, p_y, p_width, p_height )
{
	
	var l_current;
	var l_right = p_width + p_x;
	var l_down = p_height + p_y;
	var l_children = new Array();
	var l_nodeTable = new Array( this );
	var l_loop = true;
	
	
	while( l_loop )
	{
		l_current = l_nodeTable.shift();
		l_loop = ( l_nodeTable.length > 0 );
		
		
		if( l_current.y > l_down )
			continue;
		
		if( l_current.x > l_right )
			continue;
		
		
		if( l_current.y + l_current.height < p_y )
			continue;
			
		if( l_current.x + l_current.width < p_x )
			continue;	
			
		
		
		if( l_current.isLeaf )
		{
			l_children = l_children.concat( l_current.children );
		}
		else
		{
			l_nodeTable.push( l_current.front );
			l_nodeTable.push( l_current.back );
			l_loop = true;
		}
		
	}
	
	return l_children;

	
};


BSPTree.prototype.getVisibleChildrenRecursive 	= function( p_x, p_y, p_width, p_height, p_exact )
{
	var l_children = this.getChildrenIn( p_x, p_y, p_width, p_height );
	return l_children;
};


BSPTree.prototype.getChildrenIn 				= function( p_x, p_y, p_width, p_height )
{
	
	var l_right = p_width + p_x;
	var l_down = p_height + p_y;
	var l_return = new Array();
	
	
	if( this.x + this.width < p_x )
	{
		return l_return;
	}
	
	if( this.x > l_right )
	{
		return l_return;
	}
	
	if( this.y + this.height < p_y )
	{
		return l_return;
	}
	
	if( this.y > l_down )
	{
		return l_return;
	}
	
	
	if( this.isLeaf )
	{					
		return this.children;
	}
	else
	{
		l_return = l_return.concat( this.front.getChildrenIn( p_x, p_y, p_width, p_height ) );
		l_return = l_return.concat( this.back.getChildrenIn( p_x, p_y, p_width, p_height ) );
		
		return l_return;
	}

};


BSPTree.prototype.depthWalk 					= function()
{
	var l_walk = this.rdepthWalk( this );
	return l_walk;
};


BSPTree.prototype.rdepthWalk 					= function( p_node )
{
	var l_walk = new Array();
	var l_current = p_node;
	
	if ( l_current == null || l_current.isLeaf )
	{
		return l_walk;
	}
	
	l_walk.push( l_current.back );
	l_walk = l_walk.concat( this.rdepthWalk( l_current.back ) );
	l_walk.push( l_current.front );
	l_walk = l_walk.concat( this.rdepthWalk( l_current.front ) );
	
	return l_walk;
};		


// filter
BSPTree.prototype.filter						= function( p_children, p_x, p_y, p_width, p_height )
{
	var visibles = new Array();
	var i = 0;
	var j = 0;
	var max = p_children.length; 
	
	for( i = 0; i < max; i++ )
	{
		obj = p_children[i];
		
		if( obj.x + obj.width < p_x )
			continue;
			
		if( obj.y + obj.height < p_y )
			continue;
			
		if( obj.x > p_x + p_width )
			continue;
			
		if( obj.y > p_y + p_height )
			continue;
		
		visibles[j] = obj;
		j++;
	}
	
	return visibles;
}



// debug
BSPTree.prototype.dumpXML 						= function( p_nodeName )
{
	
	var l_tabs = "";
	var l_nodeName = ( typeof(p_nodeName) == "undefined" ) ? "racine" : p_nodeName;
	var l_xml = "<"+l_nodeName+" numChildren=\""+this.children.length+"\"";
	var l_child;
	var i = 0;
	var l_max = 0;
	
	l_xml += " isLeaf=\""+this.isLeaf+"\"";
	l_xml += " n=\""+this.n+"\"";
	l_xml += " x=\""+this.x+"\"";
	l_xml += " y=\""+this.y+"\"";
	l_xml += " width=\""+this.width+"\"";
	l_xml += " height=\""+this.height+"\"";
	
	if( this.axis == BSPTree.Y_AXIS )
	{
		l_xml += " yLimit=\""+ (this.y + ( this.height / 2 ) )+"\"";
	}
	else
	{
		l_xml += " xLimit=\""+ ( this.x + ( this.width / 2 ) )+"\"";
	}
	l_xml += " axis=\""+this.axis+"\">";
	
	if( this.back != null )
	{
		l_xml += this.back.dumpXML("back");
	}
	
	if( this.front != null )
	{
		l_xml += this.front.dumpXML("front");
	}
	
	if( this.children.length > 0 )
	{
		l_max = this.children.length;
		
		l_xml += "<children>";
		
		for( i = 0; i < l_max; i++ )
		{
			l_child = this.children[i];
			
			l_xml += "<child x=\""+l_child.x+"\" y=\""+l_child.y+"\" width=\""+l_child.width+"\" height=\""+l_child.height+"\" offsetX=\""+l_child.offsetX+"\" offsetY=\""+l_child.offsetY+"\"></child>";
		}
		
		l_xml += "</children>";
	}
	l_xml += "</"+l_nodeName+">";
	
	return l_xml;
	
	
	
};


//clean
BSPTree.prototype.clean 						= function()
{
	if( !this.isLeaf )
	{
		this.back.clean();
		this.front.clean();
	}
	
	this.children = new Array();
};


//destroy
BSPTree.prototype.destroy 						= function()
{
	if( !this.isLeaf )
	{
		this.back.destroy();
		this.front.destroy();
	}
	
	var l_prop = "";
	
	for( l_prop in this )
	{
		this[l_prop] = null;
	}
	
};
